With electronic automatic data processing (ADP) expanding into virtually every sphere of societal activity, and with the increasing accessibility of data through interconnected computer networks, the need to protect stored information and to allow local and remote users to communicate securely both on and off-line has become critical. In response to this need, there has been a growing awareness that, for many applications, data encryption offers the only effective means of protecting information. The first applications of the encryption of unclassified data were in the area of electronic funds transfer. The passage of the Privacy Act of 1974 (5 USC 522a) and the issuance of Transmittal Memorandum No. 1 by the Office of Management and Budget to its Circular A-71 have placed added responsibilities on Federal data systems for the protection of nonfinancial data as well.
Conventionally, data encryption entails the use of a cryptographic function such as a cryptoalgorithm that transforms the data to an unintelligible form, called cipher, using a complex series of transformations and substitutions. The cryptoalgorithm is tailored to specific users by means of individual cryptographic keys. An encryption algorithm incorporating a user selected key is used to disguise (encrypt) the data. With nonpublic key cryptoalgorithms, the key used to encrypt data is also used to decrypt data. Only a holder of the key has the capability to unscramble (decrypt) the cipher. In public key systems the decryption key is not equal to, and cannot be computed from, the encryption key. Encryption keys may be made public while decryption keys are kept secret. Cryptographic keys are often stored in and transferred through areas to which unauthorized parties may have access. At such times keys traditionally have been encrypted, using another key, so as to prevent their disclosure.
In 1977 the U.S. National Bureau of Standards (NBS) published a completely defined nonpublic key cryptoalgorithm known as the Data Encryption Standard (DES) which became the Federal standard for protection of unclassified data. The DES cryptoalgorithm is described in Federal Information Processing Standards Publication (FIPS PUB) 46, National Technical Information Service (1977) and in U.S. Pat. Nos. 3,796,830 (Smith) and 3,798,359 (Feistel), each of which is hereby incorporated herein by reference. However, even before the DES was adopted, it was clear that there was more to cryptographic security than a secure encryption algorithm. Efforts were initiated by NBS to have additional standards, based on the DES, developed. An area which needed to be addressed was secure key management. DES keys are 64-bit binary vectors which are individually selected in order to provide the unknown quantity necessary for security in the encryption algorithm. Key management involves the secure generation, distribution, storage and destruction of cryptographic keys. If the key management is weak, then the most secure cryptoalgorithm will be of little value. In fact, a very strong cryptoalgorithm used in a weak key management system can give a false sense of security.
Ideally, a secure key management system for ADP applications (1) allows secure on-line communication between any two users at speeds sufficient for normal network communications; (2) allows secure off-line communication, for example, via encrypted mail, without the need for an interactive key exchanging system in which the receipt of keys can be immediately acknowledged; (3) protects files against unauthorized disclosure; (4) provides a "digital signature" capability; (5) protects against key substitution; (6) allows data to be authenticated; and (7) allows system users to be authenticated.
An example of a prior art key management system, which employs a host master key to encrypt other keys, is described in Ehrsam et al, "A Cryptographic Key Management Scheme For Implementing the Data Encryption Standard, " 17 IBM Systems Journal 106 (1978). However, in such conventional cryptographic systems, encryption alone of a cryptographic key only prevents key disclosure, and not key substitution, i.e., the replacement of one encrypted key by another either unintentionally or intentionally. Since the replacement key may be controlled by an unauthorized party, substitution may result in the compromise of encrypted data without the disclosure of any keys.
Digital signatures were developed in conjunction with public key systems, and are used to prove that a message was sent by a specific user (the transmitter or encryptor) to another specific user (the receiver or decryptor.) A digital signature is transformed using the secret decryption key of the transmitter and is sent to the receiver. The receiver may encrypt, using the public key, and verify the signature, but the signature cannot be forged since only the transmitter knows the secret decryption key. (The cryptoalgorithm must have the property that decryption of the signature followed by encryption equals the original signature.) It has been shown that nonpublic key algorithms can also be used for digital signatures in conjunction with a "Network Registry," see Popek, et al., "Encryption Protocols, Public Key Algorithms and Digital Signatures in Computer Networks," Foundations of Secure Computation, Academic Press (1978). However, heretofore digital signatures have required special computations not normally used for all messages and often greatly expand the signature size upon transmission.